/**
 * 汉诺塔问题：
 *      有三根柱子，第一根柱子放有从下往上按大小顺序摆放的圆盘，第二个柱子是临时存放点，第三根柱子是目的点。
 * 需要把所有的圆盘从第一根柱子移动到第三根柱子，规定在小圆盘上不能放大圆盘并且在三根柱子之间一次只能移动一个圆盘。
 * 思路：
 *      假如有n个盘子，我们可以分解成三个大步骤：想办法将最上面的n-1个盘子放到临时点b处，然后将最底下的最大的盘子从
 * 源地点a移到目标地点c处，最后想办法将临时点b处的n个盘子移到目标地点c处。(用3个或者4个盘子移动可以验证)
 *      仔细想一下，将最上面的n-1个盘子放到临时点b处是不是可以理解为，b作为终点c作为临时点，n-1个盘子根据汉诺塔
 * 规则从a移动到b；而将临时点b处的n个盘子移到目标地点c处是不是可以理解为，b作为源地点a作为临时点，n-1个盘子根据
 * 汉诺塔规则从b移动到c。
 *      总的来说就是两个递归加一个a到c的移动
 * @param plates 几个盘子
 * @param source 源地点a
 * @param helper 临时存放点b
 * @param dest 目标地点c
 * @param moves 存储移动的步骤
 */
export function hanoi(
    plates: number,
    source: string,
    helper: string,
    dest: string,
    moves: string[][] = [],
) {
    if (plates <= 0) {
        return moves;
    }
    if (plates === 1) {
        // 只有一个盘子就是从a移动到c
        moves.push([source, dest]);
    } else {
        // 递归，b作为终点c作为临时点
        hanoi(plates - 1, source, dest, helper, moves);
        // 最大的盘子从a移动到c
        moves.push([source, dest]);
        // 递归，b作为源地点a作为临时点
        hanoi(plates - 1, helper, source, dest, moves);
    }
    return moves;
}

import Stack from '../data-structures/stack-object';

function towerOfHanoi(
    plates: number,
    source: Stack<number>,
    helper: Stack<number>,
    dest: Stack<number>,
    sourceName: string, helperName: string, destName: string,
    moves: any[] = [],
) {
    if (plates <= 0) {
        return moves;
    }
    if (plates === 1) {
        dest.push(source.pop());
        const move: any = {};
        move[sourceName] = source.toString();
        move[helperName] = helper.toString();
        move[destName] = dest.toString();
        moves.push(move);
    } else {
        towerOfHanoi(plates - 1, source, dest, helper, sourceName, destName, helperName, moves);
        dest.push(source.pop());
        const move: any = {};
        move[sourceName] = source.toString();
        move[helperName] = helper.toString();
        move[destName] = dest.toString();
        moves.push(move);
        towerOfHanoi(plates - 1, helper, source, dest, helperName, sourceName, destName, moves);
    }
    return moves;
}

export function hanoiStack(plates: number) {
    const source = new Stack<number>();
    const dest = new Stack<number>();
    const helper = new Stack<number>();

    for (let i = plates; i > 0; i--) {
        source.push(i);
    }

    return towerOfHanoi(plates, source, helper, dest, 'source', 'helper', 'dest');
}
